package leetcode

import (
	"math"
)

// Problem https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/
type Problem string

// strStr brute force.
func strStr(haystack string, needle string) int {
	for left, right := 0, len(needle)-1; right < len(haystack); left, right = left+1, right+1 {
		if haystack[left:right+1] == needle {
			return left
		}
	}
	return -1
}

// strStr Rabin-Karp Algorithm.
func strStr2(haystack string, needle string) int {
	hashNeedle := 0
	Q, RL, needleLen := math.MaxInt32, 1, len(needle)
	for _, c := range needle {
		hashNeedle = ((hashNeedle*256)%Q + int(c)) % Q
	}
	for i := 0; i < needleLen-1; i++ {
		RL = (RL * 256) % Q
	}
	hashHaystack := 0
	for left, right := 0, 0; right < len(haystack); right++ {
		hashHaystack = ((hashHaystack*256)%Q + int(haystack[right])) % Q
		if right-left+1 == needleLen {
			if hashHaystack == hashNeedle {
				if haystack[left:right+1] == needle {
					return left
				}
			}
			hashHaystack = (hashHaystack - (RL * int(haystack[left]) % Q) + Q) % Q
			left++
		}
	}
	return -1
}

// func main() {
// 	s1, s2 := "hello", "ll"
// 	fmt.Println(strStr(s1, s2))
// }
